1. Field of the Invention
The present invention relates to arithmetic encoding and arithmetic decoding of image or data, in particular, for example, relates to an encoding apparatus, a decoding apparatus, an encoding/decoding apparatus, an encoding method and a decoding method.
2. Description of the Related Art
FIG. 39 is an explanatory drawing of a concept of arithmetic encoding.
In FIG. 39, an effective region on a number line is divided into two partial region as an MPS (more probable symbol) partial region and an LPS (less probable symbol) partial region. Encoding is implemented by updating the effective region with one of the partial regions corresponding to a new symbol. However, the more a region range decreases, the more the numbers of effective bits of a lower limit value and an upper limit value increase as shown by binary decimals (fixed decimal) in FIG. 39, so that a register is required to have a certain precision for an operation.
In the description of the present application, a term xe2x80x9ceffective regionxe2x80x9d means a range (region) specified on a number line which may include arithmetic codes (coordinates) generated by dividing or updating data according to repeatedly encoding. Once the effective region is updated, the generated arithmetic code (coordinate) is never mapped within the range (region) on the number line other than the updated effective region.
In this case, even if the number of the effective digits increases, the high order digits seldom change. Considering this, as shown in FIG. 40, a renormalization is implemented to keep the decimal part to have the precision of dividing the region (in case of FIG. 40, 3 digits) and to flush the high order digits to integral part.
In FIG. 40, the effective region range A is made at least 4 corresponding to xc2xd (a half of the effective region range) and at most 8 (only initial value is 8) corresponding to 1 (a whole size of the effective region range) by extending to power of 2 times by the renormalization process. When the lower limit value (code) is assumed to be C, the effective region can be expressed by at least C and less than C+A.
An encoder and a decoder using arithmetic encoding and decoding can be embodied using the tables and the processing flows described in the International Standard Recommendation T. 82 of ITU-T (International Telecommunication Union). In the following explanation, the arithmetic encoding is referred to as a QM-Coder, the encoder is as an encoding section 1A and the decoder is a decoding section 16A. FIGS. 41 and 42 show general configurations of the encoder and the decoder.
In FIG. 41, the encoding section 1A receives two inputs, one of which is a CX (context) 2 and the other is an encoding PIX pixel) 3. The encoding section 1A outputs a code (code) 4A. In FIG. 42, the decoding section 16A receives two inputs, one of which is a CX (context) 2 and the other is a code 4A. The decoding section 16A outputs the PIX 3 decoded.
Data memory 5 accumulates images 6. The data memory 5 generates the context CX2 (10 bits, a total of 1024 patterns), which is a common reference pattern of 10 adjacent pixels, already encoded/decoded, indicated by Model Template for an encoding/decoding pixel. The data memory 5 also outputs the encoding pixel at the time of encoding, and accumulates decoded pixels at the time of decoding.
The QM-Coder selects either of 2-line and 3-line standard model templates for generating the context CX2 as shown in FIG. 43 and informs of the selected standard model templates from the encoder to the decoder using a predetermined header information.
In the QM-Coder, a prediction matching probability of pixel value is estimated for each context of each encoding/decoding pixel, and encoding/decoding is performed by learning the change of the prediction matching probability of pixel value. Learning is implemented by rewriting a learning memory consisting of two variable tables having indexes of contexts. One of the two variable tables is an MPS table 7 storing a pixel value MPS (More Probable Symbol), which has a high probability of occurrence, as a prediction value of one bit. (A pixel having a less probability of occurrence is called LPS (Less Probable Symbol)). The other of the two variable tables is an ST table 8 storing a state number (0-112) of 7 bits. This state number is for classifying the state of matching probability of the prediction value into total of 113 states. Initial values for the MPS table 7 and the ST table 8 are all xe2x80x9c0xe2x80x9d.
The QM-Coder includes a probability estimation table consisting of four constant tables for referring state number (state) on encoding/decoding as an index other than the above two variable tables of the learning memory.
The four constant tables are an LSZ table 9 storing LSZ value which shows an LPS region range by 16 bits, an NMPS table 10 showing a next state of MPS transition by 7 bits, an NLPS table 11 showing a next state of LPS transition by 7 bits, and an SWTCH table 12 showing an inversion of prediction value by one bit. FIG. 44 shows values set in the constant tables (These names expressed by capital alphabet letters for variable and constant tables will be used as array names in processing flow explained below.)
The LSZ table 9 is referred to by an operating unit of an arithmetic encoder 13A/an arithmetic decoder 17A and is not directly related to learning of adaptive prediction. In the arithmetic encoder 13A/the arithmetic decoder 17A, a calculation is operated using the LSZ value of the LSZ table 9, and when an operation precision is reduced, the operation is renormalized. When the renormalization occurs, learning is instructed at the same time.
On encoding, the pixel-to-symbol converter 15 detects match/mismatch between the MPS value supplied from the MPS table 7 using the context CX2 as an index and the pixel value PIX 3. The pixel-to-symbol converter 15 outputs binary symbol 14 which is a result of the detection of match/mismatch to the arithmetic encoder 13A, the learning memory (the MPS table 7 and the ST table 8) and leaning is performed by the learning instruction.
On decoding, the symbol-to-pixel converter 18 converts the symbol (the MPS or the LPS) into the pixel and outputs the obtained pixel to the data memory 5 based on the binary symbol 14 decoded by the arithmetic decoder 17A showing match/mismatch between the MPS value supplied from the MPS table using the CX2 as the index and the pixel PIX 3 to be decoded. When the MPS value and the PIX 3 match, the symbol-to-pixel converter 18 outputs the MPS value to the data memory 5 as the PIX 3. On the contrary, the symbol-to-pixel converter 18 outputs the LPS value (=1xe2x88x92MPS) when the MPS value and the PIX 3 do not match. The binary symbol 14 is also supplied to the learning memory (the MPS table 7 and the ST table 8) and learning is performed by the learning instruction.
When the learning is instructed, if the encoding/decoding binary symbol 14 is MPS, the value of the NMPS table 10 is written in the ST table 8. If the encoding/decoding binary symbol 14 is LPS, the value of the NLPS table 11 is written in the ST table 8. The state transition is thus performed. When learning is performed by LPS, if the prediction matching probability is xc2xd, the MPS value is inverted (operation xe2x80x9c1xe2x88x92MPSxe2x80x9d) and the inverted value is written in the MPS table 7. It is detected whether the prediction matching probability is xc2xd or not using the SWTCH value as a flag.
In the arithmetic encoder 13A, encoding operation is implemented by a C register 30A showing a code (a lower limit value of the region) and an A register 31 showing a region range using inputs of the LSZ value 9 and the binary symbol 14. The CT counter 50 controls output timing of the code of byte unit. Undetermined code having probability of carry-over is waiting at a BUFFER 51 and an SC counter until the code is determined and the determined code is output as a code 4A.
In the arithmetic decoder 17A, the CT counter 50 controls input timing of the code of byte unit using inputs of the LSZ value 9 and the code 4A. Decoding operation is implemented by a C register 30B showing a dislocation from the lower limit value of the region to the code 4A and an A register 31 showing the region range through a BUFFER 51 to output the binary symbol 14.
A detailed operation inside of the blocks and among the blocks configured as shown in FIGS. 41 and 42 will be explained by following flow charts of FIGS. 46 through 62.
Before explaining an encoding processing flow and a decoding processing flow, bit assignments of an encoding register (C register) 30A, a decoding register (C register) 30B and a region range register (A register) 31 are shown in FIG. 45.
In the encoding register (C) 30A, a decimal point is placed between 15th bit and 16th bit, xe2x80x9cxxe2x80x9d (16 bits) shows a calculation part Cx32 for the LSZ 9. If the calculation results in carry-over, the bits of xe2x80x9cxxe2x80x9d is propagated to the high order bit. xe2x80x9csxe2x80x9d (3 bits) shows a spacer bit part Cs33, xe2x80x9cbxe2x80x9d (8 bits) shows a byte output part Cb34, and xe2x80x9ccxe2x80x9d (1 bit) is a carry detector Cc35. In the encoding process, the value of the C register is updated to the lower limit value of the range corresponding to the encoded symbol as the code 4.
In the decoding register (C) 30B, a low-order word CLOW 36 and a high-order word CHIGH 38 can be embodied by the registers of 32 bits. A decimal is set at position upper to the bit 31, which is MSB (Most Significant Bit). xe2x80x9cbxe2x80x9d (8 bits) is a high-order byte Cb37 of the byte inputting part (CLOW register 36), and xe2x80x9cxxe2x80x9d (16 bits) is calculating part Cx (CHIGH register 38) 39 corresponding to the LSZ 9. In the decoding process, the value of the C register is updated to an offset value of the code 4, which is coordinate of the region, from the lower limit value of the region corresponding to the decoded symbol.
The region range register (A) 31 is commonly used for the encoding and decoding processes. A decimal is set corresponding to the decimal of the encoding register 30A/the C register 30B, and xe2x80x9caxe2x80x9d (16 bits) is placed as decimal part corresponding to the register part xe2x80x9cxxe2x80x9d. At initial state, the integer part (bit 16) becomes xe2x80x9c1xe2x80x9d. The region range (also called as xe2x80x9cregion sizexe2x80x9d) is updated to A-LSZ (lower partial region range) or LPZ (upper partial region range). The region range register (A) 31 is renormalized so that bit 15 showing weight of xc2xd becomes xe2x80x9c1xe2x80x9d except the initial value (the integer part xe2x80x9c1xe2x80x9d). It is guaranteed that the lower partial region is obtained even if any LSZ 9 is selected as the upper partial region range by keeping the weigh more than xc2xd. In the renormalization, the A register 31 and the C register 30A or 30B are extended by shift operation simultaneously.
In the QM-Coder, the upper partial region LSZ 9, which is fixed size for any state, is usually assigned to LPS. When the lower partial region becomes smaller than the upper partial region, the upper partial region is assigned to MPS by xe2x80x9cconditioning MPS/LPS exchangexe2x80x9d. On encoding/decoding LPS, or encoding/decoding MPS by applying xe2x80x9cconditional MPS/LPS exchangexe2x80x9d, renormalization is always implemented.
The encoding/decoding processing flow will be explained according to the bit arrangement of the register. In the processing flow, a term xe2x80x9clayer (of the resolution)xe2x80x9d in case of hierarchical encoding and xe2x80x9cstripexe2x80x9d means xe2x80x9cstripexe2x80x9d of the image divided by N line unit (only the last stripe may have lines equal to or less than N lines, or N=1). Here, it is assumed that the number of layers is 1 and stripe equals line (N=1), however, this encoding/decoding process can be applied to a plurality of layers.
The following auxiliary variables CT50, BUFFER 51, SC 52, and TEMP 53 are used for explaining the encoding/decoding process as well as variables, tables, and registers described above in the explanation of FIGS. 41, 42 and 45. The auxiliary variable CT50 counts the number of shifts by the renormalizaion implemented in the C registers 30A, 30B and the A register 31. When the value becomes xe2x80x9c0xe2x80x9d, the CT50 is used for inputting/outputting byte of a next code. The auxiliary variable BUFFER 51 stores byte value of the code supplied from the C register 30A and stores byte value of the code input to the C register 30B. The SC 52 is used only for encoding, and counts the number byte value of 0xFF continuously occur in the code output from the C register 30A.
In this specification, a value starting with a prefix xe2x80x9c0xxe2x80x9d indicates hexadecimal number. The TEMP 53 is used only for encoding, and detects the carry to the BUFFER 51, obtains the low order 8 bits of the carry-over number as a new value of the BUFFER 51. The BUFFER 51 is set by the C register 30A through the TEMP 53. The BUFFER 51 never becomes 0xFF without the carry-over. In case of the carry-over to the high order bits, the bits, the order of which is lower than the BUFFER 51, namely, the BUFFER 51 and SC 52 number of 0xFF, may be changed. Accordingly, the code output from the C register 30A cannot be determined as the code 4.
FIG. 46 is a flowchart showing a general encoding process of the ENCODER.
In this processing flow of the International Standard Recommendation T. 82, prediction process for TP (Typical Prediction) and DP (Deterministic Prediction) is shown. Process for TP and DP is not directly related to the present invention nor the conventional art, thus an explanation for TP and DP is omitted. First, at step S101, INITENC is called to perform initialization of encoding process. At step S102, a pair of the pixel PIX and the context CX is read one by one to be encoded by the ENCODE process at step S103. At step S104, S102 and S103 are repeated until the stripe (here, line) is finished to be supplied. Further, at step S105, encoding process for stripe is performed repeatedly from S102 through S104 until the image is finished to be supplied. Finally, FLUSH is called to perform termination process at step S106.
FIG. 47 is a flowchart showing ENCODE processing flow. In this flow, a process to be called is switched based on match or mismatch between the encoding pixel value 3 and the prediction value 7.
At step S111, match or mismatch between the pixel value 3 and the prediction value 7 is detected. When match is detected (xe2x80x9cYesxe2x80x9d at step S111), the encoder encodes MPS, and when mismatch is detected (xe2x80x9cNoxe2x80x9d at step S111), the encoder encodes LPS. At step S113, CODEMPS is called to encode MPS, and at step S112, CODELPS is called to encode LPS.
FIG. 48 is a flowchart showing CODELPS processing flow. The CODELPS is called for encoding LPS, namely, the mismatch is detected between the encoding pixel value 3 and the prediction value 7.
At step S121, the value of the A register 31 is temporarily updated to the lower partial region range. If step S122 results in xe2x80x9cYesxe2x80x9d, conditional MPS/LPS exchange is applied. Namely, the value of the A register 31 is unchanged to encode the lower partial region and the C register 30A is not updated. If step S122 results in xe2x80x9cNoxe2x80x9d, the upper partial region is encoded. That is, at step S123, the C register 30A showing the lower limit value is updated and at step S 124, the A register 31 showing the region range is updated. When the constant SWTCH value 12 equals xe2x80x9c1xe2x80x9d at step S125, the prediction value (MPS table) is inverted or updated at step S126. In LPS encoding, the state transition referring to the NLPS table 11 is performed at step S127. At step S128, renormalization is implemented by calling RENORME.
FIG. 49 is a flowchart showing CODEMPS processing flow. The CODEMPS is called for encoding MPS, that is, the encoding pixel value 3 matches to the prediction value 7.
First, at step S131, the value of the A register 31 is temporarily updated to the lower partial region range. If step S132 results in xe2x80x9cNoxe2x80x9d, the CODEMPS process terminates with this step. If step S132 results in xe2x80x9cYesxe2x80x9d, the state transition is always implemented referring to the NMPS table 10 at step S136. And at step S137, the renormalization is implemented by calling RENORME. Before steps S136 and 137, if step S133 results in xe2x80x9cYesxe2x80x9d, the A register 21 does not change for encoding the lower partial region and the C register 30A is not updated. If step S133 results in xe2x80x9cNoxe2x80x9d, conditional MPS/LPS exchange is applied and the upper partial region is encoded. At step S134, the C register 30A is updated and the A register 31 is updated at step S135.
FIG. 50 shows RENORME processing flow for implementing the renormalization.
To shift the value of the A register 31 and the C register 30A to higher order by 1 bit respectively at steps S141 and S142 means to perform an operation equal to the multiplication by 2. At step S143, 1 is subtracted from the variable CT50 and at step S144, it is checked whether the variable CT50 is xe2x80x9c0xe2x80x9d or not. If step S144 results in xe2x80x9cYesxe2x80x9d, BYTEOUT process is called at step S145 and the C register 30A outputs the code 4 of one byte. At step S146, completion of the renormalization is detected. If the value of the A register 31 is less than 0x8000, steps S141 through S145 are repeated. If the value of the A register 31 is equal to or more than 0x8000, the renormalization process is completed.
FIG. 51 shows BYTEOUT processing flow for outputting the code 4 byte by byte from the C register 30A.
A byte output section Cb 34 of the C register 30A is to be output. The carry detector Cc 35 operates at the same time for detecting carry-over. At step S151, 9 bits of the sum of the Cb register 34 and the Cc register 35 are set to the variable TEMP 53. The byte output is processed by three ways based on the check at steps S152 and S159. Namely, a case where the carry-over has occurred at step S152 (TEMP greater than 0x100; Cc=1), a case where the carry-over has not occurred and TEMP=0xFF, and a case where the carry-over has not occurred and TEMP less than 0xFF. If step S152 results in xe2x80x9cYesxe2x80x9d, at step S153, the code already output from the C register 30A and stored as the BUFFER 51 and carry value 1 is determined as a code. At step S154, SC 52 number of byte value 0 (stacked 0xFF has been converted into 0x00 by the carry) is written and xe2x80x9cSC+1xe2x80x9d bytes of the code value with carry-over is determined.
At step S155, the variable SC 52 is set to xe2x80x9c0xe2x80x9d and at step S156, the low order 8 bits of the variable TEMP are set to the variable BUFFER 51. At step S157, the Cc register 35 and the Cb register 34, which are processed as variable TEMP 53, are cleared. At step S158, xe2x80x9c8xe2x80x9d is set to the variable CT 50 for processing 8 bits until a next byte is output. If step S159 results in xe2x80x9cYesxe2x80x9d, the code 4 cannot be determined and the variable SC 52 is incremented by xe2x80x9c1xe2x80x9d to accumulate 0xFF. If step S159 results in xe2x80x9cNoxe2x80x9d, the code 4 already output from the C register 30A is written as the value of the BUFFER 51 at step S153 At step S154, SC 52 number of byte value 0xFF are written and the code value of xe2x80x9cSC+1xe2x80x9d bytes is determined as the code value. At step S163, the variable SC 52 is set to xe2x80x9c0xe2x80x9d and at step S164, the variable TEMP 53 (8 bits, without carry-over) is set to the variable BUFFER 51.
FIG. 52 shows INITENC processing flow for setting the initial values of the ST table 8, the MPS table 7 and each variable at starting time of the encoding.
In the figure, at step S171, xe2x80x9cthe first stripe of this layerxe2x80x9d means xe2x80x9cstarting time of encoding an imagexe2x80x9d when the image does not include a concept of layer or stripe. In case of an image consisting of a plurality of stripes, processing can be continued without initializing the variable tables for each stripe At step S171, it is checked if this is the first stripe of the pixel of this layer or forced reset of the tables.
If step S171 results in xe2x80x9cYesxe2x80x9d, the ST table 8 and the MPS table 7, which are the variable tables for all the contexts CX2, are initialized at step S172. The SC 52, the A register 31, the C register 30A and the variable CT 50 are initialized at steps S173, S174, S175 and S176, respectively. The initial value 11 of the CT50 is the sum of the number of bits of the Cb register 34 and the number of bits of the Cs register 33. After processing 11 bits, the first code is output. If step S171 results in xe2x80x9cNoxe2x80x9d, the table values at the end of the previous stripe of the same layer are set to the variable tables at step S177 instead of the initialization.
FIG. 53 shows FLUSH processing flow for implementing termination process including sweeping out the remaining value in the C register 30A.
At step S181, CLEARBITS is called to minimize the number of effective bits of the code remaining in the C register 30A. At step S182, FINALWRITES is called to finally output the variable BUFFER 51, SC 52 and the code 4, which has been undetermined and is now determined, of the C register 30A. At step S183, the first byte of the code 4 is removed because the variable BUFFER 51 is output (as integer part of the code) prior to the value output from the C register 30A. At step S184, the consecutive bytes xe2x80x9c0x00xe2x80x9d at the end of the code 4 can be removed, if desired, because the code 4 is decimal coordinates within the final effective range.
FIG. 54 shows CLEARBITS processing flow for minimizing the number of effective bits of the code 4 at the end of encoding.
By this process, the code 4 is determined to be the value that ends with the greatest possible number of xe2x80x9c0x00xe2x80x9d. At step S191, the variable TEMP 53 is set to the value obtained by clearing the low-order two bytes (Cx register 32) of the upper limit value of the final effective range. At step S192, it is checked if the value obtained by clearing the low-order two bytes of the upper limit value is larger than the value of the C register 30A. If step S192 results in xe2x80x9cYesxe2x80x9d, overcleared bytes are returned to the variable TEMP 53 at step S193 and the value of the C register 30A is set to the value after returning the overcleared byte. If step S192 results in xe2x80x9cNoxe2x80x9d, the value of the variable TEMP 53 is set in the C register 30A.
FIG. 55 shows FINALWRITES processing flow for writing the code determined at the end of encoding including remaining value in the C register 30A.
At step S201, the C register is shifted by the number of bits shown by the values of the variable CT50 to enable to output the code and to detect the carry-over. At step S202, it is checked if the carry-over has occurred or not. If step S202 results in xe2x80x9cYesxe2x80x9d, the carry-over has occurred and if xe2x80x9cNoxe2x80x9d, the carry-over has not occurred. As well as in the BYTEOUT processing flow, the code of xe2x80x9cSC+1xe2x80x9d bytes is determined by writing the code value already output from the C register 30A at steps S203 and S204 for the code value with the carry or at steps S207 and S208 for the code value without the carry. At step S205, the register Cb 34 value (1 byte), and at step S206, the code is finished to be output by outputting the low-order 1 byte of the register Cb 34 value.
FIG. 56 shows DECODER processing flow illustrating a whole decoding process.
In processing flow of the International Standard Recommendation T. 82, processes for TP (Typical Prediction) and DP (Deterministic Prediction) is not directly related to the present invention nor the conventional arts (the first and the second related arts), thus an explanation is omitted. First, at step S211, INITDEC is called to initialize the decoding process. At step S212, the contexts CX2 is read one by one. At step S213, the pixel PIX 3 is decoded by the process DECODE. At step S214, steps S212 and S213 will be repeated until the stripe (in this case, line) is finished to be supplied. Further, at step S215, decoding process for stripe is repeated from steps S212 through S214 until the image is finished to be supplied.
FIG. 57 shows DECODE processing flow for decoding the decoding pixel.
First, at step S221, the value of the A register 31 is temporarily updated by the lower partial region range. If step S222 results in xe2x80x9cYesxe2x80x9d, the lower partial region is decoded. If step S223 results in xe2x80x9cYesxe2x80x9d, MPS_EXCHANGE is called at step S224 and RENORMD is called at step S225 to implement the renormalization. If step S223 results in xe2x80x9cNoxe2x80x9d, the MPS is decoded without implementing the renormalization, and the prediction value 7 is taken as the pixel value 3. If step S222 results in xe2x80x9cNoxe2x80x9d, the upper partial region is decoded. LPS_EXCHANGE is called at step S227 and RENORMD is called at step S228 to implement the renormalization. In the path for calling MPS_EXCHANGE and LPS_EXCHANGE, even if the decoding region is determined, it is impossible to know which should be decoded between MPS and LPS without detecting which region is larger, MPS or LPS. Accordingly, each pixel value 3 is determined by the called processing flow.
FIG. 58 shows LPS_EXCHANGE processing flow for decoding the upper partial region. If step S231 results in xe2x80x9cYesxe2x80x9d, the MPS is decoded. At step S232, the C register 30B is updated and the A register 31 is updated at step S233. At step S234, the prediction value 7 is determined as the pixel value 3 without any change. At step S235, a state is moved to a next state by referring to the NMPS table 10. If step S231 results in xe2x80x9cNoxe2x80x9d, the LPS is decoded. At step S236, the C register 30B is updated and the A register 31 is updated at step S237. At step S238, non-prediction value xe2x80x9c1xe2x80x94prediction valuexe2x80x9d is determined as the pixel value 3. If step S239 results in xe2x80x9cYesxe2x80x9d, the prediction value (MPS table) 7 is inverted or updated at step S240. At step S241, a state is moved to a next state by referring to the NLPS table 11.
FIG. 59 shows MPS_EXCHANGE processing flow for decoding the lower partial region. If step S251 results in xe2x80x9cYesxe2x80x9d, the LPS is decoded. At step S252, non-prediction value is determined as the pixel value 3. If step S253 results in xe2x80x9cYesxe2x80x9d, the prediction value MPS table) is inverted or updated at step S254. At step S255, a state is moved to a next state by referring to the NLPS table 11. If step S251 results in xe2x80x9cNoxe2x80x9d, the MPS is decoded. At step S256, the prediction value 7 is determined as the pixel value 3 without any change. At step S257, a state is moved to a next state by referring to the NMPS table 10.
FIG. 60 shows RENORMD processing flow for implementing renormalization.
At step S261, it is checked whether the value of the variable CT50 is 0 or not. If step S261 results in xe2x80x9cYesxe2x80x9d, BYTEIN is called so as to input the code 4 of one byte into the C register 30B at step S262. At step S263, the A register 32 is shifted to higher-order by 1 bit and the C register 30B is shifted to higher-order by 1 bit at step S264. This shifting operation equals to duplication. At step S265, 1 is subtracted from the variable CT50. At step S266, it is checked whether the renormalization is completed, that is, the value of the A register 31 is less than 0x8000, or not. If the value of the A register 32 is less than 0x8000, steps S261 through S265 are repeated. At step S267, it is checked whether the value of the variable CT50 is 0 or not. If step S267 results in xe2x80x9cYesxe2x80x9d, BYTEIN is called so as to input the code of one byte into the C register 30B.
FIG. 61 shows BYTEIN processing flow for reading the code 4 into the C register 30B byte by byte.
In the figure, xe2x80x9cSCDxe2x80x9d (Stripe Coded Data) is the code 4 for stripe. If step S271 results in xe2x80x9cYesxe2x80x9d, no code 4 is to be read at step S272, and the variable BUFFER 51 is set to xe2x80x9c0xe2x80x9d. At step S273, the value of the variable BUFFER 51 is read into the CLOW register 36 (Cb 37), and at step S274, the variable CT50 is set to xe2x80x9c8xe2x80x9d for processing the code of 8 bits until a next code is input. If step S271 results in xe2x80x9cNoxe2x80x9d, the code 4 of one byte is read from the xe2x80x9cSCDxe2x80x9d into the variable BUFFER 51 at step S275.
FIG. 62 shows INITDEC processing flow for setting initial values of the ST table 8, the MPS table 7 and each variable at starting time of the decoding.
Initialization of the table values of steps S281, S282 and S290 are the same as ones of steps S171, S172 and S177 of INITENC processing flow in the encoding process. The initial value of the C register 30B is set by inserting 3 bytes of the code 4 into the Cx register 39 and the Cb register 37. At step S283, the C register 30B is cleared, and at step S284, BYTEIN is called so as to insert 1 byte of the code 4 into the Cb register 37. At step S285, the C register 30B is shifted by 8 bits, and at step S286, BYTEIN is called so as to insert 1 byte of the code 4 into the Cb register 37. At step S287, the C register 30B is shifted by 8 bits, and at step S288, BYTEIN is called so as to insert 1 byte of the code 4 into the Cb register 37. By these steps, the sum of 3 bytes of the code 4 is set in the Cx register 39 and the Cb register 37. The initial value of the A register 31 is set at step S289.
In the following, the second related art will be explained.
An encoder and a decoder for arithmetic encoding according to the second related art are embodied by applying tables and flowcharts explaining processes described in the Japanese Patent No. 2755091.
In the arithmetic encoding system, which outputs the code by byte unit, when the output byte value is 0xFF, the code value cannot be determined because the carry afterwards may propagate to the higher bit which has been already output. Accordingly, it is forced to determine whether the carry-over occurs or not if there is possibility of the carry propagated to the effective region when the output byte value becomes 0xFF.
FIG. 63 shows a conception to forcibly determine whether the carry-over occurs or not.
In the figure, the lower limit value C is the value of the encoding register (C register) 30A, and the upper limit value U60 is the sum of the lower limit value C30A and the effective partial region range A (the value of the A register) 31. It is judged that the carry-over occurs when the lower limit value does not match the most significant bit of the upper limit value, and then it is judged a value of a carry boundary T61 exists within the effective region.
The effective region is divided by the carry boundary value into two partial regions called xe2x80x9ca carry regionxe2x80x9d where the carry-over occurs and xe2x80x9ca carryless regionxe2x80x9d where the carry-over does not occur. A carry region range R162 is shown as (U-T) and a carryless region range R063 is shown as (T-C). Whether the carry-over occurs or not is determined by detecting a case the effective region completely match the carry region or the carryless region, or detecting a case the effective region is included in the carryless region or the carry region. Here, it is assumed one of the partial regions of the effective region is truncated and the other of the partial regions is made to be a new effective region. On truncation of the partial region, it is preferable to truncate a smaller partial region for reducing the loss of code length. In the figure, the partial region R063, which is smaller than the partial region R162, is truncated. By truncation of the partial region, it becomes necessary to check the necessity of renormalization of the new effective region. Such a method for controlling the carry of the arithmetic encoding system is called adaptive region truncation system.
FIGS. 64 and 65 respectively show rough sketch of the configuration of an encoding section 1B and a decoding section 16B of the arithmetic encoding system which employs adaptive region truncation system.
FIG. 64 corresponds to FIG. 41 of the first related art and shows the encoding section 1B provided by altering an arithmetic encoder 13B and a code 4B. FIG. 65 corresponds to FIG. 42 of the first related art and shows the decoding section 16B provided by altering an arithmetic decoder 17B and the code 4B. The data flows among the blocks including these altered elements and learning is implemented in the same way as the conventional cases shown in FIGS. 41 and 42.
In the arithmetic encoder 13B, an encoding operation is initiated in the C register 30A and the A register 31 by inputting the LSZ value 9 and the binary symbol 14. The CT counter 50 controls the timing for outputting the code by byte unit. Synchronized with outputting the code, the carry boundary within the region is detected by a U register 60, a T register 61, an R1 register 62, and an R0 register 63. When the carry boundary is detected, the values of the C register 30A and the A register 31 are modified to forcibly determine if the carry-over occurs or not by applying the adaptive region truncation system. The carry is propagated to the BUFFER 51 at maximum to output a definite code, namely, the code 4B.
In the arithmetic decoder 17B, the CT counter 50 controls the timing for inputting the code by byte unit with inputting the LSZ value 9 and the code 4B. Synchronized with inputting the code, the carry boundary within the region is detected by a D register 64, which is reproduced from the encoding register 30A, the U register 60, the R1 register 62, and the R0 register 63. When the carry boundary is detected, the values of the C register 30A, the D register 64 and the A register 31 are modified by applying the adaptive region truncation system. The decoding operation proceeds by the C register 30B, the A register 31 and the D register 64 through the BUFFER 51 to output the binary symbol 14.
A detailed operation within the blocks and among the blocks of the configurations shown in FIGS. 64 and 65 will be explained using flowcharts of FIGS. 46 through 49, 53, 54, 56, 57 and 59 explaining the operation of first related art, which has been described, and flowcharts of FIGS. 67 through 76, which will be described later.
FIG. 66 shows the encoding register used in the adaptive region truncation system.
In this register, the Cs register 33 is eliminated compared with the encoding register shown in FIG. 45 referred in the description of the above first related art. This is because outputting the byte from the encoder and inputting the byte to the decoder should be synchronized, and the adaptive region truncation is also synchronized with inputting/outputting the byte. In encoding (encoder), the value of the encoding register is updated by the lower limit value of the effective region, and in decoding (decoder), the value of the encoding register is updated by displacement (offset) from the lower limit value of the effective region to the code value. Accordingly, on decoding, the value of the encoding register of the encoder should be reproduced in the decoder to precisely detect the carry boundary. In decoding process, this value is held by the D register 64 having the same configuration with the encoding register of the encoder.
An operation of the second related art will be described in reference to flowcharts explaining processes modified from or added to the operation of the first related art.
The adaptive region truncation system will be described by adding necessary modifications to the flowcharts explaining encoding/decoding process of the QM-Coder described in the above first related art. The operations of FIGS. 46 through 49, 53 and 54 relating to the encoder and FIGS. 56, 57 and 59 relating to the decoder will be the same with ones explained in the first related art by referring to the flowcharts. The upper limit value U60 of the effective region, the carry boundary value T61, the carryless region range R063, the carry region range R162, and the D register 64 are additionally employed for the explanation of the operation as variables.
FIG. 67 is a flowchart explaining RENORME process for performing the renormahzation.
Compared with the flowchart (FIG. 50) of the first related art, a step S147 for calling ROUNDOFFE process is added for detecting whether the adaptive region truncation process is applied or not. A step for calling BYTEOUT process (S145 of FIG. 50) is included in the ROUNDOFFE process.
FIG. 68 is a flowchart explaining ROUNDOFFE process for implementing the adaptive region truncation process.
At step S301, it is checked if the output byte value is 0xFF or not. If S301 results in xe2x80x9cNoxe2x80x9d, the ROUNDOFFE process terminates with this step. If S301 results in xe2x80x9cYesxe2x80x9d, the carry boundary value T61 (constant) is set at step S302, and the carryless region range R063 is set at step S303. At step S304, the carryless region range R063 is compared with the region range (the value of the A register). If the value R063 is not smaller than the value of the A register 31 or the value R063 is not larger than 0 (S304 results in xe2x80x9cNoxe2x80x9d), the carry boundary T61 is not within the effective region and the process terminates with this step. If the value R063 is smaller than the value of the A register 31 and the value R063 is larger than 0 (S304 results in xe2x80x9cYesxe2x80x9d), at step S305, the upper limit value U60 is set, and the carry region range R162 is set at step S306. At step S307, the value R063 is smaller than the value R162 (S307 results in xe2x80x9cYesxe2x80x9d), the lower limit value is updated by the carry boundary value at step S308 and the value R1 is set in the region range register (the value of the A register) at step S309 so that the carry region is made be the effective region. If the value R063 is larger than the value R162 (S307 results in xe2x80x9cNoxe2x80x9d), the value R063 is set in the region range (the value of the A register) 31 at step S309 so that the carryless region is made be the effective region. Finally, BYTEOUT process is called at step S311.
FIGS. 69, 70 and 71 respectively show flowcharts explaining BYTEOUT process, INITENC process, and FINALWRITES process. As different points from FIGS. 51, 52 and 55 corresponding figures of the first related art, the number of masking or shifting is changed for steps S151xe2x80x2 and S157xe2x80x2 of FIG. 69 (flowchart of BYTEOUT), step S176xe2x80x2 of FIG. 70 (flowchart of INTENC), and steps S202xe2x80x2, S205xe2x80x2 and step S206xe2x80x2 of FIG. 71 (flowcharts of FINALWRITES) because of the elimination of the Cs register part 33 of the encoding register.
In FIG. 68 (flowchart of ROUNDOFFE), whether the carry propagates or not has been already determined when the output byte value is 0xFF, thus the variable BUFFER can be output serially. The checking step S159 becomes unnecessary in FIG. 69 (flowchart of BYTEOUT). Similarly, the variable SC itself and steps concerning the variable SC such as steps S154, S155, S160, S162, S163 of FIG. 69 (flowchart of BYTEOUT), S173 of FIG. 70 (flowchart of INITENC), and S204, S208 of FIG. 71 (flowchart of FINALWRITES) become unnecessary.
FIG. 72 shows a flowchart explaining LPS_EXCHANGE process for decoding the upper region. Compared with the flowchart of the first related art (FIG. 58), steps S242, S243 are added for reproducing the encoding register as the D register in the decoder.
FIG. 73 shows a flowchart explaining RENORMD process for performing renormalization.
Compared with the flowchart of the first related art (FIG. 60), steps S269 for reproducing the encoding register as the D register and S270 for calling the ROUNDOFFD process to detect whether the adaptive region truncation is applied or not are added, and step for calling the BYTEOUT process (step S262 of FIG. 60) is included in the ROUNDOFFD process. Since steps S261 and S267 are removed for eliminating redundancy of checking, the flowchart of FIG. 73 has a different shape from the flowchart of FIG. 60, however, the operation of the process is the same.
FIG. 74 shows a flowchart explaining ROUNDOFFD process for applying the adaptive region truncation.
Compared with the ROUNDOFFE process of FIG. 68, the encoding register includes the variable D64 instead of C30A. Steps S321 through S331 correspond to steps S301 through S311. A step S332 is added for applying the adaptive region truncation process to the encoding register 30B of the decoder (the register D64) corresponding to the encoding register 30A of the encoder. Finally, the BYTEIN process is called at step S331 instead of the BYTEOUT process (step S311) of FIG. 68.
FIGS. 75 and 76 respectively show flowcharts for explaining the BYTEIN process and the INITDEC process. Compared with flowcharts of FIGS. 61 and 62, a step S276 is added to FIG. 75, and a step S290 is added in FIG. 76 for initialization of reproducing the encoding register 30A of the encoder as the D register 64 in the decoder.
There are some problems in the above related arts as described in the following.
In the encoder of the first related art, in case the code value cannot be determined because whether the carry-over occurs or not is not resolved, the code length of the waiting code is stored in the counter. However, the data length is not limited, so that the overflow may occur from the counter.
Further, there is a problem that delay time due to determination of the code cannot be estimated when the data length is not known because the code cannot be output until the code value has been finally determined.
Further, when the code value is finally determined for the waiting code having long code length, it is required a long time to output the code, which may suspend the encoding process at all or temporalily.
On the other hand, as for the encoder of the second related art, there is a problem that it is checked to control the carry by the value of the encoding register, and the carry boundary should be calculated precisely.
In the decoder of the second related art, there is a problem that it cannot be checked properly to control the carry unless the encoding register of the encoder is reproduced in the decoder.
The present invention is provided to solve the above-mentioned problems of the related arts. The invention aims, for example, to estimate the definite delay time for determining the code by eliminating the overflow of the counter storing the code length of the code which is waiting until the code is determined, and by controlling the carry with forcibly determining the code at proper interval. The invention also aims to reduce the code length and the time required for outputting the code by converting the code value into a predetermined pattern.
Further, the invention also aims to control the carry without precisely calculating the carry boundary and without reproducing the encoding register of the encoder in the decoder.
According to the present invention, an encoding apparatus having
a data memory accumulating information source data and outputting encoding data and its auxiliary parameter (context),
a learning memory accumulating and outputting learning data relating the encoding data specified by the auxiliary parameter,
a probability estimation table outputting an encoding parameter specified by the learning data, and
an encoder operating an arithmetic encoding based on the encoding data and the encoding parameter and outputting a code,
the encoding apparatus includes:
a synchronization detector measuring and informing of one of inputting a predetermined unit of the information source data and outputting a predetermined unit of the code as a predetermined interval; and
a carry boundary detector detecting a carry boundary value at the predetermined interval within an effective region and indicating to truncate a part of the effective region based on a result of detection;
wherein the encoder truncates one of equally divided upper and lower partial regions of the effective region indicated by the carry boundary detector and updates the effective region.
According to another aspect of the invention, a decoding apparatus having
a data memory outputting an auxiliary parameter (context) for decoding data and accumulating the decoding data decoded to output as an information source data,
a learning memory accumulating and outputting learning data relating the decoding data specified by the auxiliary parameter,
a probability estimation table outputting a decoding parameter specified by the learning data, and
a decoder operating an arithmetic decoding based on the decoding parameter and a code and outputting the decoding data,
the decoding apparatus includes:
a synchronization detector measuring and informing of one of outputting a predetermined unit of the information source data and inputting a predetermined unit of the code as a predetermined interval; and
a carry boundary detector detecting a carry boundary within an effective region at the predetermined interval and indicating to truncate a part of the effective region based on a result of detection;
wherein the decoder updates the effective region by truncating one of equally divided upper and lower partial regions of the effective region which does not include a code value of the carry boundary detected.
According to another aspect of the invention, an encoding method includes:
(a) accumulating information source data and outputting encoding data and its auxiliary parameter (context);
(b) accumulating and outputting learning data relating the encoding data specified by the auxiliary parameter;
(c) outputting an encoding parameter specified by the learning data;
(d) operating an arithmetic encoding based on the encoding data and the encoding parameter and outputting a code;
(e) measuring and informing of one of inputting a predetermined unit of the information source data and outputting a predetermined unit of the code as a predetermined interval;
(f) detecting a carry boundary at the predetermined interval within an effective region and indicating to truncate a part of the effective region based on a result of detection; and
(g) truncating one of equally divided upper and lower partial regions of the effective region indicated by the step of detecting and updating the effective region.
According to another aspect of the invention, a decoding method includes:
(a) outputting an auxiliary parameter (context) for decoding data and accumulating the decoding data decoded to output as an information source data;
(b) accumulating and outputting learning data relating the decoding data specified by the auxiliary parameter;
(c) outputting a decoding parameter specified by the learning data;
(d) operating an arithmetic decoding based on the decoding parameter and a code and outputting the decoding data;
(e) measuring and informing of one of outputting a predetermined unit of the information source data and inputting a predetermined unit of the code as a predetermined interval;
(f) detecting a carry boundary within an effective region at the predetermined interval and indicating to truncate a part of the effective region based on a result of detection; and
(g) truncating one of equally divided upper and lower partial regions of the effective region and updating the effective region.